#ifndef __CACHE_H__
#define __CACHE_H__

#include <iostream>
#include <utility>
#include <map>
#include <queue> 

using namespace std;

/**
* Cache del index set y del sequence set
* ______________________________________
* 
* La idea aqui es tener las posiciones mas solicitadas asociadas al bloque correspondiente. A medida que se leen bloques se agregan al cache, indexados por la posicion en el archivo del index set o del seuqence set:
* 
* map<long,BloqueIndexSet<Clave>>
* 
* o
* 
* map<long,BloqueSequenceSet<Clave,Dato>>
* 
* En caso de sufrir alguna modificacion algun bloque que se encuentre en el cache, se actualizara el mismo sin actualizar el archivo correspondiente.
* 
* Suponiendo que el cache esta lleno y hay que agregar un nuevo bloque, habra que eliminar un elemento del map. Es por esto que hay que tener un sistema que decida que posicion es la mas leida (o menos leida). Podriamos tener una cola de posiciones leidas donde si agregamos un bloque en el cache, habra que agregar en la cola la posicion, y en un map aparte, la posicion junto con la cantidad de veces que se leyo el bloque del cache. Luego al sacar una posicion de la cola y leer la cantidad del map, si la cantidad-1 es cero entonces ese es el bloque a eliminar, sino restamos uno a la cantidad y sacamos otra posicion de la cola. Por tanto tendiamos:
* 
* // Posiciones agregadas al map
* queue<long>
* 
* // Cantidad de veces que se agrego la posicion a la cola.
* map<long,long>
* 
* 
* Vemos que estariamos utilizando tres estructuras (con la anterior) para el cache, pero tranquilamente podriamos tener dos:
* 
* // En este map tenemos asociada la posiocion del bloque con el bloque y una especie de puntaje que depende de la cantidad de veces que lleva accedido el mismo desde que esta en el cache (suma) y la cantidad de veces que fue sacado de la cola (resta).
* map<long,pair<BloqueIndexSet<Clave,Dato>,long>>
* 
* // Cola con las posiciones de los bloques cada vez que se accede a los mismos. Tener en cuenta que el hecho de agregarlos en el map cuenta como acceso.
* queue<long> 
* 
* Como podemos ver esto tambien aplica para los bloques del sequence set.
* 
* Tener en cuenta que cuando se elimina un bloque, se lo debe eliminar del map. Por ende puede suceder que se saque una posicion de la cola que no exista en el map.
* 
* Tambien tener en cuenta que el bloque se escribe en el archivo una vez que se quita del cache, esto puede ser porque salio de la cola y el puntaje es cero, o porque se llamo al destructor del arbol.
*/

template<class Clave,class Dato>
class Cache;

template<class Clave,class Dato>
ostream &operator<<(ostream &os,Cache<Clave,Dato> &cache);

template<class Clave,class Dato>
class Cache
{
	public:
	
	Cache(const long cantidadMaximaClaves):
	actual(this->datos.end()),
	cantidadMaximaClaves(cantidadMaximaClaves)
	{
	}
	
	/**
	 * Obtiene el dato para la clave pasada. Si existe se incrementa el
	 * puntaje.
	 * @param dato Dato asociado a la clave.
	 * @param clave Clave a ser buscada. 
	 * @return true si encontro la clave, sino false.
	 */
	bool get(Dato &dato,const Clave &clave)
	{
		typename map<Clave,pair<Dato,int> >::iterator i;
		
		// Se verifica si la clave existe.
		i=this->datos.find(clave);
		
		bool encontrado=i!=this->datos.end();
		
		// En caso de haber encontrado la clave...
		if (encontrado)
		{			
			// Se incrementa el puntaje para la clave.
			i->second.second++;
			
			// Se ascienta el acceso.
			this->accesos.push(clave);
			
			// Se obtienen los datos asociados a la clave.
			dato=i->second.first;
		}
		
		return encontrado;
	}
	
	/**
	 * Si existe la clave, se actualiza con el dato pasado. Si no existe, se
	 * la agrega con el dato pasado. Se incrementa el puntaje de la clave en 
	 * caso de existir, sino se le asigna el puntaje inicial. 
	 * En caso de tener que agregar la clave y estar lleno this, se eliminara 
	 * la clave de menor puntaje que tiene una mayor cantidad de tiempo sin ser 
	 * accedida.
	 * @param clave Clave a ser actualizada o agregada.
	 * @param dato Dato asociado a la clave.
	 */
	void update(const Clave &clave,const Dato &dato,Clave &claveEliminada,
		Dato &datoEliminado,bool &eliminacionClave)
	{
		typename map<Clave,pair<Dato,int> >::iterator i;
		
		eliminacionClave=false;
		
		// Se verifica si la clave existe.
		i=this->datos.find(clave);
		
		bool encontrado=i!=this->datos.end();
		
		// En caso de no haber sido encontrada la clave...
		if (!encontrado)
		{
			// ...en caso de estar lleno el cache...
			if (eliminacionClave = (this->lleno()) )
				// ...se elimina la clave de menor puntaje que tiene una mayor
				// cantidad de tiempo sin ser accedida.
				this->hacerEspacio(claveEliminada,datoEliminado);
				
			// Se agrega la clave.
			this->datos[clave];

			// Se obtiene un iterador de la clave recien insertada.			 
			i=this->datos.find(clave);

			// Se setea el puntaje inicial.
			i->second.second=0;
		}
		
		// Se incrementa el puntaje para la clave.
		i->second.second++;
		
		// Se actualizan los datos asociados a la clave.
		i->second.first=dato;

		// Se ascienta el acceso a la clave.
		this->accesos.push(clave);
	}
	
	/**
	 * Indica si this esta lleno.
	 * @return true si esta lleno, sino false.
	 */
	bool lleno()
	{
		return ((long)this->datos.size())==this->cantidadMaximaClaves;
	}
	
	/**
	 * Se elimina la clave de menor puntaje que tiene una mayor cantidad de 
	 * tiempo sin ser accedida.
	 */
	void hacerEspacio(Clave &claveEliminada,Dato &datoEliminado)
	{
		bool eliminada=false;
		
		while (!eliminada)
		{
			Clave clave;
			
			// Se obtiene la clave que hace mayor tiempo fue accedida.
			clave=accesos.front();
			
			// Se elimina de la cola.
			accesos.pop();
			
			typename map<Clave,pair<Dato,int> >::iterator i;
			
			// Se busca la clave.
			i=this->datos.find(clave);
			
			// En caso de haberla encontrado...
			if (i!=this->datos.end())
			{
				// Se obtiene el puntaje de dicha clave y se lo decrementa.
				i->second.second--;
				
				// En caso de ser cero su puntaje...
				if (eliminada=(i->second.second==0))
				{
					// Se obtiene la clave eliminada.
					claveEliminada=i->first;
					
					// Se obtiene el dato eliminado.
					datoEliminado=i->second.first;
					
					// ...se elimina dicha clave.
					this->datos.erase(i);
				}
			}
		}
	}

	/**
	 * Se elimina la clave pasada de this.
	 */	
	void erase(const Clave &clave)
	{
		this->datos.erase(clave);
	}
	
	void first()
	{
		this->actual=this->datos.begin();
	} 
	
	void next()
	{
		this->actual++;
	}
	
	bool eof() const
	{
		return this->actual==this->datos.end();
	}
	
	void getDato(Dato &dato)
	{
		dato=this->actual->second.first;
	}
	
	protected:
	
	// Datos asociados a un puntaje, indexados por una clave. 
	map<Clave,pair<Dato,int> > datos;
	
	typename map<Clave,pair<Dato,int> >::iterator actual;
	
	// Cola con el orden en que se fue accediendo a las claves.
	queue<Clave> accesos;
	
	long cantidadMaximaClaves;
	
	friend ostream &operator<<<Clave,Dato>(ostream &os,
		Cache<Clave,Dato> &cache);

};

template<class Clave,class Dato>
ostream &operator<<(ostream &os,Cache<Clave,Dato> &cache)
{
	// Se muestran las claves, datos y puntajes...
	typename map<Clave,pair<Dato,int> >::const_iterator
		i;
	
	os << "datos" << endl << "{" << endl;
	for (i=cache.datos.begin();i!=cache.datos.end();i++)
		os << "{clave=" << i->first << "; dato=" << i->second.first <<
			"; puntaje=" <<  i->second.second << "}" << endl;
	os << "}" << endl;

	// Se muestra la cola de accesos...

	os << "Cola de accesos" << endl << "{" << endl;
	os << "{Elemento mas viejo=" << cache.accesos.front() << "}" << endl;
	os << "{Elemento mas reciente=" << cache.accesos.back() << "}" << endl;
	os << "}" << endl;
	
	return os;
}

#endif
